home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / listings / v_09_08 / 9n08129a < prev    next >
Text File  |  1991-06-16  |  3KB  |  101 lines
  1. /*
  2. l_distance ()   Determines to what extent two character strings
  3.                 are (un)equal using the 'Levenstein distance'
  4.                 algorithm.
  5.  
  6. Limitation:     For memory space conservation and execution speed
  7.                 this implementation compares the first 20
  8.                 characters of both strings only if longer strings
  9.                 are supplied to l_distance ().
  10.                 '#define COMP_LEN' may be changed to decrease or
  11.                 increase the number of characters compared.
  12.  
  13.                 De-commenting the following '#define DEBUG' will
  14.                 create a stand-alone program, which enables you
  15.                 to experiment with different values for the
  16.                 constants 'ADDITION', 'CHANGE' and 'DELETION'.
  17. */
  18.  
  19. /* #define DEBUG */
  20.  
  21. #include <stdlib.h>
  22. #include <string.h>
  23.  
  24. #ifdef DEBUG
  25. #include <stdio.h>
  26. #define PRINTF  printf
  27. #define PRINTF2 printf
  28. #else
  29. #define PRINTF(_a)
  30. #define PRINTF2(_a,_b)
  31. #endif
  32.  
  33. #define ADDITION        1               /* change constants in this block */
  34. #define CHANGE          3               /* of four lines if needed.       */
  35. #define DELETION        5
  36. #define COMP_LEN        20
  37.  
  38. #define ARR_SIZE                COMP_LEN + 1
  39. #define SMALLEST_OF(x,y,z)      ( (x<y) ? min (x,z) : min (y,z) )
  40. #define ZERO_IF_EQUAL(x,y)      ( requested[x-1] == found[y-1] ? 0 : CHANGE)
  41.  
  42.  
  43. int l_distance (char *requested, char *found)
  44. {
  45.         int i, r_len, f_len;
  46.         register int j, itmp, idist, iprev;
  47.         int     distance [ARR_SIZE];
  48.  
  49.         if ((r_len = strlen (requested)) > COMP_LEN)
  50.                 r_len = COMP_LEN;
  51.         if ((f_len = strlen (found))     > COMP_LEN)
  52.                 f_len = COMP_LEN;
  53.  
  54.         PRINTF ("\n");
  55.         distance[0] = itmp = 0;
  56.         for (j = 1; j <= ARR_SIZE; j++)
  57.                 distance[j] = itmp += ADDITION;
  58.         for (i = 1; i <= r_len; i++) {
  59.                 iprev = distance[0] + DELETION;
  60.                 for (j = 1; j <= f_len; j++, iprev = idist)     {
  61.                         idist = iprev + ADDITION;
  62.                         if ((itmp = distance [j-1] + ZERO_IF_EQUAL(i,j)) < idist)
  63.                                 idist = itmp;
  64.                         distance [j-1] = iprev;
  65.                         if ((itmp = distance[j] + DELETION) < idist)
  66.                                 idist = itmp;
  67.                         PRINTF2 (" %3d", idist);
  68.                 }
  69.                 distance [f_len] = idist;
  70.                 PRINTF ("\n");
  71.         }
  72.  
  73.         return idist;
  74. }
  75.  
  76. #ifdef DEBUG
  77. void usage ()
  78. {
  79.     printf("\nUsage:  LD requested found\n");
  80.         printf("\n        requested & found are the two strings");
  81.         printf("\n        to be compared with the Levenstein distance");
  82.     printf("\n        algorithm.\n\n");
  83. }
  84.  
  85. int main (int argc, char *argv [])
  86. {
  87.     int result;
  88.  
  89.     if (argc != 3) {
  90.         usage ();
  91.         exit (1);
  92.     } else {
  93.         printf ("\nComparing '%s' and '%s':\n", argv[1], argv[2]);
  94.         result = l_distance (argv[1], argv[2]);
  95.         printf ("\nResult = %d\n", result);
  96.     }
  97.     return (0);
  98. }
  99. #endif
  100.  
  101.